Modern databases can include a very large number of database entries. Accordingly, it is important to use efficient techniques to identify the locations of desired database entries. Such techniques include the use of B+ trees. A B+ tree is a data structure comprising a set of data pages and one or more interior pages. Data pages are leaf nodes of the B+ tree and interior pages are non-leaf nodes of the B+ tree. The data pages contain the database entries of the database. The interior pages do not contain database entries, but rather contain information that enables a computing system to identify locations of desired database entries. For example, each of the interior pages contains a set of nodes. Each node in an interior page includes a key value and a reference. The key value specifies a value of a field of the database entries and the reference specifies another page in the B+ tree. The key values are ordered within an interior page in a predictable way. For example, if the key values are integers, the key values may be ordered within the interior page according to increasing numerical value.
When a computing system is attempting to identify the memory address of a desired database entry having a field specifying a particular value, the computing system identifies a node in an interior page having the highest-ordered key value that is less than or equal to the particular value. For example, if the particular value is 8 and the interior page has nodes having key values 3, 4, 7 and 9, the computing system identifies the node having the key value 7. After identifying the node, the computing system retrieves the page in the B+ tree indicated by the reference of the node. If the retrieved page is an interior page, the process repeats and the computing system retrieves another page in the B+ tree. If the retrieved page is a data page, the computing system identifies the desired database entry within the data page and returns the desired database entry.
Each of the pages have a fixed size. For example, each of the pages may have a size of 32 kilobytes (KB). In many instances, there are not enough nodes in the interior pages to completely fill the interior pages or not enough database entries in the data pages to completely fill the data pages. For example, an interior page may have a fixed size of 32 KB, but only contain 20 KB of data. In this example, the remaining 12 KB is unused free space.